﻿#pragma once
#include<iostream>
#include<vector>
using namespace std;
/// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，

namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{
		}
	};
	 //K 为 T 中key的类型
	 //T 可能是键值对，也可能是K
	 //KeyOfT: 从T中提取key
	 //Hash将key转化为整形，因为哈市函数使用除留余数法
	template<class K>
	class HashFuc
	{
	public:
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	template<>
	class HashFuc<string>
	{
	public:
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash *= 31;
				hash += e;
			}

			return hash;
		}
	};
	template <class K, class T, class KeyOfValue, class HF>
	struct HBIterator;
	template<class K, class T, class KeyOfT, class Hash = HashFuc<K>>
	class  HashBucket
	{
	public:
		typedef HashNode<T> Node;
		//template <class K, class T, class KeyOfValue, class HF>
		typedef struct HBIterator<K, T, KeyOfT, Hash> Iterator;
		friend struct HBIterator< K,T,KeyOfT,Hash>;
		
		HashBucket()
		{
			_tables.resize(10, nullptr);
		}
		HashBucket(size_t n)
		{
			_tables.resize(n, nullptr);
		}
		// 哈希桶的销毁
		~HashBucket()
		{
			size_t size = _tables.size();
			for (size_t i = 0;i < size;i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
			}
		}

		// 插入值为data的元素，如果data存在则不插入
		pair<Iterator, bool> Insert(const T& data)
		{
			Hash fuc;
			KeyOfT kof;
			size_t hashi = fuc(kof(data)) % _tables.size();
			// 存在
			Iterator it = Find(kof(data));
			if (it != end())
				return make_pair(it, false);

			// 不存在
				//扩容
			size_t size = _tables.size();
			if (10 * _n / size >= 7)
			{
				size_t newsize = size * 2;
				HashBucket<K, T, KeyOfT, Hash> newhash(newsize);
				//遍历表
				for (size_t i = 0;i < size;i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						newhash.Insert(cur->_data);
						cur = cur->_next;
					}
				}
				_tables.swap(newhash._tables);

			}
			//插入

			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			_n++;
			return make_pair(Iterator(newnode, this), true);

		}

		// 在哈希桶中查找值为key的元素，存在返回true否则返回false﻿
		Iterator Find(const K& key)
		{
			Hash fuc;
			KeyOfT kof;
			size_t hashi = fuc(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{

				if (kof(cur->_data) == key)
				{
					return Iterator(cur, this);
				}
				cur = cur->_next;
			}
			return Iterator();

		}
		size_t Count(const K& key)const
		{
			return Find(key)!=end();
		}
		 //哈希桶中删除key的元素，删除成功返回true，否则返回false
		Iterator Erase(const K& key)
		{
			Hash fuc;
			KeyOfT kof;
			size_t hashi = fuc(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (kof(cur->_data) == key)
				{
					Node* next = cur->_next;
					delete cur;
					if (prev)
						prev->_next = next;
					else
						_tables[hashi] = next;
					if (next)
					{
						hashi++;
						while (_tables[hashi] == nullptr)
							hashi++;
						return Iterator(_tables[hashi], this);
					}
					return Iterator(next,this);

				}
				prev = cur;
				cur = cur->_next;
			}
			return Iterator();
		}
		size_t HashFunc(const K& key)const
		{
			return Hash()(key)% _tables.size();
		}
		size_t bucketcount()const
		{
			return _tables.size();
		}
		size_t bucketsize(const K& key)const
		{
			size_t count;
			Hash fuc;
			count = fuc(key) % _tables.size();
			return count;
		}
		Iterator begin()
		{
			Node* cur;
			for (size_t i = 0;i < _tables.size();i++)
			{
				cur = _tables[i];
				if (cur)
					return Iterator(cur, this);
			}
			return Iterator();
		}
		Iterator end()
		{
			return Iterator();
		}
		size_t size()const
		{
			return _tables.size();
		}
		bool empty()const
		{
			return _tables.empty();
		}
	private:
		vector<Node*> _tables;  // 指针数组
		size_t _n = 0;			// 表中存储数据个数
	};
	// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
	template <class K, class T, class KeyOfValue, class HF>
	struct HBIterator
	{
		typedef HashBucket<K, T, KeyOfValue, HF> HashBucket;
		typedef HashNode<T>* PNode;
		typedef HBIterator<K, T, KeyOfValue, HF> Self;

		HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr)
			:_pNode(pNode)
			, _pHt(pHt)
		{
		}
		Self& operator++()
		{
			// 当前迭代器所指节点后还有节点时直接取其下一个节点
			if (_pNode->_next)
				_pNode = _pNode->_next;
			else
			{
				 //找下一个不空的桶，返回该桶中第一个节点
				size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data)) + 1;
				for (; bucketNo < _pHt->bucketcount(); ++bucketNo)
				{
					if (_pNode = _pHt->_tables[bucketNo])
						break;
				}
			}

			return *this;
		}
		Self operator++(int)
		{
			Self sf = *this;
			this->operator++();
			return sf;
		}
		T& operator*()
		{
			return this->_pNode->_data;
		}
		T* operator->()
		{
			return &this->_pNode->_data;
		}
		bool operator==(const Self& it) const
		{
			return it->_pNode == _pNode;
		}
		bool operator!=(const Self& it) const
		{
			return it._pNode != _pNode;
		}
		PNode _pNode;             // 当前迭代器关联的节点
		HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
	};
}